//法一：小根堆
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue <ListNode> heap = new PriorityQueue<>((v1,v2)->v1.val-v2.val);
        for(ListNode l:lists){
            if(l!=null)
                heap.offer(l);
        }
        ListNode newhead=new ListNode(0);
        ListNode prev=newhead;
        while(!heap.isEmpty()){
            ListNode t=heap.poll();
            prev.next=t;
            prev=t;
            if(t.next!=null)
                heap.offer(t.next);
        }
        return newhead.next;
    }
}

//法二：递归
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int l,int r){
        if(l>r) return null;
        if(l==r) return lists[l];
        int mid = (l+r)/2;
        ListNode l1=merge(lists,l,mid);
        ListNode l2=merge(lists,mid+1,r);
        return mergeTwoLists(l1,l2);
    }
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode cur1=l1,cur2=l2;
        ListNode newhead=new ListNode(0);
        ListNode prev=newhead;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next=cur1;
                prev=cur1;
                cur1=cur1.next;
            }else{
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        if(cur1!=null) prev.next=cur1;
        if(cur2!=null) prev.next=cur2;
        return newhead.next;
    }
}